12973 - 짝지어 제거하기

정보

• 문제 보기: 12973 - 짝지어 제거하기
• 소요 시간: 4분 59초
• 풀이 언어: java
• 체감 난이도: 3️⃣
• 리뷰 횟수: ✅

풀이 키워드

스포주의

스택

풀이 코드

정보

• 메모리: 98900 KB
• 시간: 82 ms

import java.util.*;

class Solution
{
    public int solution(String s)
    {
        Deque<Character> st = new ArrayDeque<>();
        for (char ch : s.toCharArray()) {
            if (st.isEmpty() || st.peek() != ch) st.push(ch);
            else st.pop();
        }
        
        return st.isEmpty() ? 1 : 0;
    }
}

풀이 해설

괄호 짝 맞추는 문제로 치환할 수 있는 유형이다.

스택이 비어있을때만 주의해주면 된다.

🧪 추가 테스트 케이스

a
답: 0

abccbcca
답: 1

다른 풀이 & 퍼포먼스 비교

스택 구현체 대신 쌩으로 인덱스를 조작하는 원포인터 방식의 구현을 해볼 수도 있다.

class Solution
{
    public int solution(String s)
    {
        char[] st = new char[s.length()];
        int i = 0; // stack pointer
        
        for (char ch : s.toCharArray()) {
            if (i < 1 || st[i-1] != ch) st[i++] = ch;
            else --i;
        }
        
        return i == 0 ? 1 : 0;
    }
}

퍼포먼스를 시각화하자면 하단과 같다.

컬렉션 프레임워크 오버헤드로 인해 둘이 비교하는 것이 미안해질 정도이다.

하지만 대회가 아닌 이상 표준 제공 자료구조를 잘 활용하는 것이 좋기에, 대부분의 코테에선 컬렉션 사용이 권장된다.

Test Case	TC 1	TC 2	TC 3	TC 4	TC 5	TC 6	TC 7	TC 8
Stack Collection	60.62	81.99	45.80	47.08	44.50	47.31	50.71	49.60
Raw Index	26.40	20.52	20.35	23.80	20.74	20.82	20.35	22.10

❌ 투포인터는 안돼요

i, j 재조정 오버헤드 때문에 TLE 터져서 안된다. 두번 다시 시간 낭비하지 말자~

(정답은 나온다...ㅋㅋㅋ 효율성 체크에서 하나 빼고 다 빠꾸먹을 뿐 😂)

class Solution
{
    public int solution(String s)
    {
        char[] sArr = s.toCharArray();
        final int n = s.length();
        
        // init pointers
        int i = 0;
        for (; i < n-1; ++i) if (sArr[i] == sArr[i+1]) break;
        int j = i+1;
        if (n-1 < j) return 0;
        
        int removed = 0;
        boolean[] visited = new boolean[n];
        //int DEBUG_CNT = 4;
        while (/*DEBUG_CNT-- > 0 &&*/ j < n) {
            //System.out.println(i + " " + j);
            
            if (i < 0 || sArr[i] != sArr[j]) {
                // 1. unmatch -> re-set i & j
                for (i = j; i < n-1; ++i) if (sArr[i] == sArr[i+1]) break;
                j = i+1;
                //System.out.println("reset: " + i + " " + j);
            }
            else {
                // 2. match -> count & re-set i & j
                //System.out.println("match: " + i + " " + j);
                visited[i] = visited[j] = true;
                removed += 2;
                while (-1 < i && visited[i]) --i;
                ++j;
            }
            
        }
        
        return removed == n ? 1 : 0;
    }
}

메모

• 단순한 문제라 한번 슥 읽어보는 식으로 복습하기